循环结构与零钱问题：多题型综合解析与应用

篇首语：本文由编程笔记#小编为大家整理，主要介绍了各题型归纳总结相关的知识，希望对你有一定的参考价值。

文章目录

• 二分
• • 两种代码模板
  • • 代码1
    • 代码2
    
    
  • 思考
  • • 有重复元素的情况
    • 山峰数组
    
    
  
  
• 动态规划
• • 从题目中辨识是否用DP
  • • 重复子问题
    • • 剑指 Offer 46. 把数字翻译成字符串
      • 91. 解码方法
      
      
    • 最优子结构
    • • 322. 零钱兑换
      • 279. 完全平方数
      • 343. 整数拆分
      • 377. 组合总和 Ⅳ
      
      
    • &＃61;&＃61;无后效性【多阶段、有约束 的决策最优化问题】&＃61;&＃61;
    • • 不同路径
      • 打家劫舍
      
      
    
    
  
  
• 贪心

两种代码模板

代码1

• 代码1&＃xff1a;在循环中查找元素
  适合知道num[mid]等于什么&＃xff0c;才能得到结果的情况

public class Solution

// 「力扣」第 704 题&＃xff1a;二分查找
public int search(int[] nums, int target)
int len &＃61; nums.length;
int left &＃61; 0;
int right &＃61; len - 1;
// 目标元素可能存在在区间 [left, right]
//区间还剩一个元素时&＃xff0c;继续循环
while (left <&＃61; right)
// 推荐的写法是 int mid &＃61; left &＃43; (right - left) / 2;
int mid &＃61; (left &＃43; right) / 2;
if (nums[mid] &＃61;&＃61; target)
return mid;
else if (nums[mid] < target)
// 目标元素可能存在在区间 [mid &＃43; 1, right]
left &＃61; mid &＃43; 1;
else
// 目标元素可能存在在区间 [left, mid - 1]
right &＃61; mid - 1;


return -1;




代码2

• 代码2&＃xff08;1&＃xff09;&＃xff1a;在循环体中排除目标元素一定不存在的区间
  适合 不知道num[mid]等于什么 才能得到结果&＃xff0c;但知道什么情况下可以缩小区间&＃xff0c;的情况。
  使用 if (nums[mid]

public class Solution

// 「力扣」第 704 题&＃xff1a;二分查找
public int search(int[] nums, int target)
int len &＃61; nums.length;
int left &＃61; 0;
int right &＃61; len - 1;
// 目标元素可能存在在区间 [left, right]
//区间还剩一个元素时&＃xff0c;退出循环
while (left < right)
int mid &＃61; left &＃43; (right - left) / 2;
//这里注意使用nums[mid]
//若使用nums[mid] > target,则mid需要上取整&＃xff1b;
if (nums[mid] < target)
// 下一轮搜索区间是 [mid &＃43; 1, right]
left &＃61; mid &＃43; 1;
else
// 下一轮搜索区间是 [left, mid]
right &＃61; mid;


if (nums[left] &＃61;&＃61; target)
return left;

return -1;




• 代码2&＃xff08;2&＃xff09;&＃xff1a;在循环体中排除目标元素一定不存在的区间

使用if (nums[mid] > target) 判断&＃xff1b;会出现left &＃61; mid&＃xff1b;mid需要上取整:int mid &＃61; left &＃43; (right - left &＃43; 1) / 2;防止死循环

即&＃xff0c;出现left &＃61; mid情况&＃xff0c;mid需向上取整int mid &＃61; left &＃43; (right - left &＃43; 1) / 2;防止死循环。

public class Solution

// 「力扣」第 704 题&＃xff1a;二分查找
public int search(int[] nums, int target)
int len &＃61; nums.length;
int left &＃61; 0;
int right &＃61; len - 1;
while (left < right)
int mid &＃61; left &＃43; (right - left &＃43; 1) / 2;
if (nums[mid] > target)
// 下一轮搜索区间是 [left, mid - 1]
right &＃61; mid - 1;
else
// 下一轮搜索区间是 [mid, right]
left &＃61; mid;


if (nums[left] &＃61;&＃61; target)
return left;

return -1;




思考

二分的思想是&＃xff0c;通过num[mid]与一个target对比&＃xff0c;来缩小区间&＃xff0c;

• 当给定target时&＃xff0c;自然与target比较&＃xff1b;
• 当未给定target时&＃xff0c;找那些和mid比较 能产生缩小区间效果的元素&＃xff0c;如&＃xff1a;左右边界常作为target&＃xff0c;

有重复元素的情况

针对有重复的情况&＃xff0c;是将下面两种**无重复情况**下的划分&＃xff1a;
nums[l] <&＃61; nums[mid]
nums[l] > nums[mid])
改为下面三种划分&＃xff0c;将等于的情况单独提取出来&＃xff0c;【适合重复情况】
nums[l] < nums[mid]
nums[l] &＃61;&＃61; nums[mid] //若nums[l]不是目标值&＃xff0c;因为相等&＃xff0c;所以可以缩小一个范围&＃xff0c;即l&＃43;&＃43;;
nums[l] > nums[mid])


在有序数组中进行查找一个数&＃xff08;二分下标&＃xff09;

在整数范围内查找一个整数&＃xff08;二分答案&＃xff09;

山峰数组

arr[mid] 与 arr[mid &＃43; 1]比较

找题目中的约束条件&＃xff0c;然后根据约束条件定义状态

• 动态规划的用途&＃xff1a;求解多阶段决策问题
  动态规划解决的是这样一类问题&＃xff1a;多阶段决策问题。这里的「阶段」就是生活语言&＃xff1a;解决一个问题分很多步骤&＃xff0c;每一个步骤又有很多种选择&＃xff0c;这一点和「回溯算法」是一样的。
  通常可以把多阶段决策问题画成一张树形图。

• 动态规划与回溯算法的区别
  「动态规划」与「回溯算法」在问题问法上的区别是&＃xff1a;「动态规划」问题通常只问结果&＃xff0c;即只问最优值是多少&＃xff0c;或者问解决方案的个数&＃xff0c;而不问具体解&＃xff08;具体的解决方案&＃xff09;是什么&＃xff1b;
  「回溯算法」问题通常让我们给出一个问题的所有解决方案&＃xff0c;要求我们返回的是一个嵌套列表。

能够使用动态规划解决的问题&＃xff0c;一定可以使用回溯算法解决。但是我们要清楚一个事实&＃xff1a;回溯算法的时间复杂度很高。在只问最优值是多少的场景下&＃xff0c;没有必要记录每个阶段的每一个步骤。动态规划方法很多时候的意义在于评估算法的上限。

从题目中辨识是否用DP

重复子问题

剑指 Offer 46. 把数字翻译成字符串

求&＃xff1a;计算一个数字有多少种不同的翻译方法。
只是求有多少种&＃xff0c;而不是求出每种的解决方案&＃xff0c;即DP。【若求所有解决方案&＃xff0c;则用回溯】

91. 解码方法

求&＃xff1a;请计算并返回 解码 方法的 总数
只是求有多少种&＃xff0c;而不是求出每种的解决方案&＃xff0c;即DP。【若求所有解决方案&＃xff0c;则用回溯】

最优子结构

它们的问法都一样&＃xff1a;求解一个问题的最优值是多少&＃xff0c;但没有问最优值是怎么来的。以后遇到这样的问题&＃xff0c;需要有一定敏感&＃xff0c;可能这个问题考察的是动态规划&＃xff08;还有可能考察广度优先遍历、贪心算法&＃xff09;。
分析最优子结构的重要方法依然是&＃xff1a;通过研究具体的例子&＃xff0c;画图分析。

322. 零钱兑换

279. 完全平方数

343. 整数拆分

377. 组合总和 Ⅳ

对于 nums &＃61; [1,2,3], target &＃61; 4
dp[4] &＃61; dp[4 - 1] &＃43; dp[4 - 2] &＃43; dp[4 - 3]
即&＃xff0c;
dp[target ] &＃61; dp[target - nums[0] ] &＃43; dp[target - nums[1] ] &＃43; dp[target - nums[2] ] &＃43; …【target - nums[2] >&＃61;0)】

class Solution
public int combinationSum4(int[] nums, int target)
int[] dp &＃61; new int[target &＃43; 1];
//dp[0]没实际意思&＃xff0c;由dp[1] &＃61; 1 &＃61; dp[0]推出&＃xff1b;
dp[0] &＃61; 1;
for(int j &＃61; 1 ; j <&＃61; target ; j&＃43;&＃43;)
for(int i &＃61; 0 ; i < nums.length ; i&＃43;&＃43;)
if(j >&＃61; nums[i]) dp[j] &＃61; dp[j] &＃43; dp[j - nums[i]];


return dp[target];




无后效性【多阶段、有约束 的决策最优化问题】

不同路径

• 只需求出路径个数&＃xff0c;不需求出具体方案&＃xff1b;

打家劫舍

• 题目只问最优值&＃xff0c;并没有问最优解&＃xff0c;因此可以考虑使用「动态规划」。
• 约束条件&＃xff1a;在不触动警报装置的情况下&＃xff0c;
  即分一个房子偷或不偷两种情况&＃xff1b;